Solinas Prime

A Solinas Prime can be written as a sum of exponents of 2, minus one.

Ideal for cryptography due to reduced computation.

You can calculate modular multiplication over one of these using only addition!

%%🖋 Edit in Excalidraw%%

I.e. you can write the large exponents in terms of smaller exponents, and you can apply this recursively to get everything in terms of one small exponent.

OpenSSL Vulnerability

OpenSSL tried to do a modular reduction by adding all the elements together, and then doing the modular reduction at the end, instead of after each addition. This would of course be more efficient.

If this function was called with deliberately designed operands, an incorrect result can be triggered, or just with very small random chance $10 * 2^{-29}$

EC-DH(e) - Elliptic Curve - Diffie-Hellman (Ephemeral)

When used in “static” mode (the default), the server re-uses the same secret key among all sessions in the same invocation of the library, to avoid the overhead of generating a secret key each time. This means that secret key is a fixed target for any attack.

In the key exchange, we have to make sure that the points we’re operating on are actually points on the curve. So we validate them before by testing if some multiplication gives the correct result.

Since the validation relies on modular multiplication, if the attacker chooses the inputs carefully, they can cause the validation to pass, while the point is actually on a different curve, not the correct one the server expects.

Similar Attack - RSA Bug Attack - Biham et. al.

If the RSA implementation uses Montgomery multiplication, it multiplies bits one at a time. We can pick a ciphertext where we’ll end up with two trigger values being multiplied at the bit we are attacking. If the bit is 1 then the multiplication will happen, and the bug will be triggered, otherwise it won’t. Then we can look at the final result of the RSA decryption and check if it’s correct to determine if the target bit was 1 or 0.